/*
 * @Author: your name
 * @Date: 2024-04-06 15:21:49
 * @LastEditTime: 2024-04-06 15:33:46
 * @LastEditors: your name
 * @Description: In User Settings Edit
 * @FilePath: \.leetcode\18.四数之和.cpp
 */
/*
 * @lc app=leetcode.cn id=18 lang=cpp
 *
 * [18] 四数之和
 */

// @lc code=start
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        for(int k = 0; k < nums.size(); k++){
            // 第一次剪枝
            if(nums[k] > target && nums[k] >= 0){
                // 这种情况说明后面不可能出现四数之和为target
                break;
            }
            // 对 nums[k]去重
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            for(int j = k+1; j < nums.size(); j++){
                // 第二次剪枝
                if(nums[k]+nums[j] > target && nums[k]+nums[j] >= 0){
                    break;
                }
                // 对nums[j]去重
                if(j > k+1 && nums[j] == nums[j-1]){
                    continue;
                }
                int left = j+1;// 第三个数
                int right = nums.size()-1;// 第四个数
                while(right > left){
                    if((long)nums[k]+nums[j]+nums[left]+nums[right] > target){
                        right--;
                    }
                    else if((long)nums[k]+nums[j]+nums[left]+nums[right] < target){
                        left++;
                    }
                    else{
                        res.push_back(vector<int>{nums[k], nums[j], nums[left], nums[right]});
                         // 对nums[left]和nums[right]去重
                        while(right > left && nums[left]== nums[left+1]) left++;
                        while(right > left && nums[right]== nums[right-1]) right--;
                         // 找到答案时，双指针同时收缩
                        right--;
                        left++;
                    }
                }
            }
        }
        return res;
    }
};
// @lc code=end
// 仿照第15题：三数之和
